package com.anjingsi.tools.algorithm;

import com.google.common.collect.Lists;
import io.swagger.models.auth.In;
import org.apache.commons.lang3.RandomUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: 二分查找算法
 * @description
 * @author: 安静思
 * @create: 2019-12-03 09:29
 **/
public class BinarySearchUtils {

    public static int binarySearch(List<Integer> list,Integer target){
        //list必须是有序的
        int low = 0 ;
        int high = list.size() - 1;
        while (low <= high){
            int middle = (low + high) >> 1;
            if(list.get(middle) > target){
                high = middle - 1;
            }else if(list.get(middle) < target) {
                low = middle + 1;
            }else {
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        List<Integer> list = Lists.newArrayList();
        for (int i = 0; i < 11; i++) {
            list.add(RandomUtils.nextInt(1,100));
        }
        System.out.println("生成的list:"+list);
        System.out.println("排序后的:"+sort(list));
        System.out.println(binarySearch(list,58));
    }

    public static List<Integer> sort(List<Integer> list){
        for (int i = 0; i < list.size(); i++) {
            for (int j = i+1; j < list.size(); j++) {
                if(list.get(i) > list.get(j)){
                    Integer mid = list.get(i);
                    list.set(i,list.get(j));
                    list.set(j,mid);
                }
            }
        }
        return list;
    }
}
